package dichotomy;

public class BSExist {

    /**
     * 在有序数组 sortedArr 中，是否存在数字num
     * 
     * @param sortedArr
     * @param num
     * @return
     */
    public static boolean exist(int[] sortedArr, int num) {
        if (sortedArr == null || sortedArr.length == 0) {
            return false;
        }
        int L = 0; // 左边界
        int R = sortedArr.length - 1; // 右边界
        int mid = 0; // 中间位置
        while (L < R) {
            /**
             * 效果等同于 mid = (L+R)/2 mid = L + (R - L)/2
             * 此种写法的目的一是为了防止 L + R 超过数据的范围(溢出)，
             * 二是 位运算效率更高 加减运算，位运算，效率比乘除效率高
             */
            mid = L + ((R - L) >> 1);
            if (sortedArr[mid] == num) {
                return true;
            } else if (sortedArr[mid] > num) { 
                R = mid - 1;
            } else {
                L = mid + 1;
            }

        }
        return sortedArr[L] == num;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        System.out.println(exist(arr, 71));
    }

}
